package 一些算法竞赛测试题;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: a
 * Date: 2022-09-29
 * Time: 23:20
 */

/*
使用贪心解决钱币找零问题
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K
元，至少要用多少张纸币？
 */

public class Demo5 {
    public static int maxNum(int money, int[][] moneyCount){
        int num = 0;
        int len = moneyCount.length;
        //首先选择最大面值的纸币
        for(int i = len - 1; i >= 0; i--){
            int c = Math.min(money / moneyCount[i][0], moneyCount[i][1]);
            money = money - c * moneyCount[i][0];
            num += c;
        }
        if(money != 0){
            return -1;
        }
        return num;
    }

    public static void main(String[] args) {
        int[][] moneyCount = {{1, 3}, {2, 1}, {5, 4}, {10, 3}, {20, 0}, {50, 1}, {100, 10}};
        //在这一步之前, moneyCount数组里面的面值可能是会无序的, 所以这里可以写一个排序的函数来对这个数组进行排序
        Arrays.sort(moneyCount, (int[] a, int[] b) -> {
            return a[0] - b[0];
        });
        for(int[] x : moneyCount){
            System.out.println(x[0] + " " + x[1]);
        }
        Scanner scanner = new Scanner(System.in);
        int money = scanner.nextInt();
        int res = maxNum(money, moneyCount);
        if(res != -1){
            System.out.println(res);
        }else{
            System.out.println("NO");
        }
    }
}
